/*
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true
 */
package LC0234;

class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution1 {
    // 链表 + 双指针

    //回文指的的是整个链表正读倒读都一样。
    //画图理解我的注解
    public boolean isPalindrome(ListNode head) {
        //如果链表为空，直接返回true，默认就是回文
        if(head == null){
            return true;
        }

        //定义一个指针，指向链表的中间节点。利用快慢指针来定位
        //将链表分为前后两个链表，
        ListNode firstTail = getFirstListNodeTail(head);

        //定义一个指针，指向后一个反转过链表的头节点
        //注意这里的两个链表经过反转，断开连接了。画图可以看出来
        ListNode secondHead = reverse(firstTail.next);
        //定义一个指针指向前一个链表的头节点
        ListNode p1 = head;
        //定义一个指针，指向后一个链表的头节点
        ListNode p2 = secondHead;
        //定义一个返回的结果
        boolean result = true;
        //当后一个链表不指向空时，就继续比较两个前后链表的节点值
        while(result && p2!=null){
            //如果两个链表的节点值不同，说明不是回文，就直接返回
            if(p1.val != p2.val){
                result = false;
            }
            //将前后链表的节点指针同时向后移动一位，继续比较
            p1 =p1.next;
            p2 =p2.next;
        }
        //将后一个链表反转回原来的链表，并连接前后链表
        firstTail.next =  reverse(secondHead);
        //将结果返回
        return result;
    }
    //返回中间节点
    public ListNode getFirstListNodeTail(ListNode head){
        //定义一个快指针和一个慢指针
        ListNode fast = head;
        ListNode slow = head;
        //只要快指针不到末尾，就继续循环
        //当链表为偶数的时候取的是第一个节点，为中间数。
        //注意区分条件；fast !=null && fast.next.next !=null这个在偶数下取的第二个节点
        while(fast.next != null && fast.next.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //当快指针到达末尾时，此时慢指针移动的位置，就是中间节点的位置
        return slow;
    }

    //反转链表
    public ListNode reverse(ListNode head){
        //当链表的为空或只有一个节点的时候，直接返回。
        if(head == null || head.next == null){
            return head;
        }
        //定义一个指针赋予null值
        ListNode prev = null;
        //定义一个指针指向链表的第一个节点
        ListNode cur = head;
        //只要不移动到链表的尾部
        while(cur != null){
            //定义一个指针指向链表的第二个节点
            ListNode next = cur.next;
            //将第一个节点指向null，断开与第二个节点的连接
            cur.next = prev;
            //将第一个指针移到第二个节点
            prev = cur;
            //将第二个指针移动到第三个节点
            cur = next;
        }
        //此时第一个指针的位置就是反转后链表的头节点。
        return prev;
    }
}
